{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最短路径问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/shortestpath.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 邻接表\n",
    "graph_dict = {0:{1:6,2:3},\n",
    "              1:{0:6,2:8,3:7,6:4},\n",
    "              2:{0:3,1:8,4:2,5:1,7:10},\n",
    "              3:{1:7},\n",
    "              4:{2:2,6:1},\n",
    "              5:{2:1,7:8},\n",
    "              6:{1:4,4:1},\n",
    "              7:{2:10,5:8}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "\n",
    "# Dijkstra算法，不断更新最近节点的相邻节点\n",
    "def dijkstra(graph_dict, start, end):\n",
    "    costs = {} # 记录每个节点的临时最短路径\n",
    "    processed = set() # 记录已经确定最短路径的节点\n",
    "    heap = []\n",
    "    costs[start] = (0, None) # 将起点信息放入costs中，格式为（距离，前节点）\n",
    "    heappush(heap, (0, start, None)) # 将起点信息放入最小堆中，格式为（距离，当前节点，前节点）\n",
    "    \n",
    "    while heap:\n",
    "        # 从堆顶取出当前最短路径\n",
    "        cost, cur_node, pre_node = heappop(heap)\n",
    "        while cur_node in processed:\n",
    "            if not heap: return None, []\n",
    "            cost, cur_node, pre_node = heappop(heap)\n",
    "        # 如果当前节点为终点，则返回最短距离和最短路径\n",
    "        if cur_node == end:\n",
    "            path = []\n",
    "            x = cur_node\n",
    "            while x is not None:\n",
    "                path.insert(0, x)\n",
    "                _, x = costs[x]\n",
    "            return cost, path\n",
    "        # 将当前节点标记为已经确定最短路径的节点\n",
    "        processed.add(cur_node)\n",
    "        # 对当前节点的所有相邻节点，更新起点到相邻节点的最短路\n",
    "        for adj_node in graph_dict[cur_node]:\n",
    "            if adj_node in processed: continue # 跳过已确定最短路径的节点\n",
    "            new_cost = cost + graph_dict[cur_node][adj_node] # 新距离 = 已确定的当前节点距离 + 邻边长度\n",
    "            if adj_node in costs and new_cost >= costs[adj_node][0]: continue # 原有路径更短则无需更新\n",
    "            costs[adj_node] = new_cost, cur_node\n",
    "            heappush(heap, (new_cost, adj_node, cur_node))\n",
    "    \n",
    "    return None, []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(8, [1, 6, 4, 2, 5])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dijkstra(graph_dict, 1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [6, 4, 2, 0])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dijkstra(graph_dict, 6, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, [0])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dijkstra(graph_dict, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Bellman算法，允许存在无环负权边，每轮更新所有边，共N-1轮次\n",
    "def bellman(graph_dict, start, end):\n",
    "    costs = {}\n",
    "    costs[start] = (0, None)\n",
    "    \n",
    "    # 循环N-1轮次\n",
    "    for time in range(len(graph_dict) - 1):\n",
    "        # 遍历已经有计算过距离的所有节点\n",
    "        for cur_node in costs.copy():\n",
    "            # 遍历当前节点的相邻节点\n",
    "            for adj_node in graph_dict[cur_node]:\n",
    "                new_cost = costs[cur_node][0] + graph_dict[cur_node][adj_node]\n",
    "                if adj_node in costs and new_cost >= costs[adj_node][0]: continue\n",
    "                costs[adj_node] = (new_cost, cur_node)\n",
    "    \n",
    "    # 回溯最短路径\n",
    "    path = []\n",
    "    x = end\n",
    "    while x is not None:\n",
    "        path.insert(0, x)\n",
    "        _, x = costs[x]\n",
    "    \n",
    "    return costs[end][0], path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(8, [1, 6, 4, 2, 5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bellman(graph_dict, 1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [6, 4, 2, 0])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bellman(graph_dict, 6, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, [0])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bellman(graph_dict, 0, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 743. 网络延迟时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有 N 个网络节点，标记为 1 到 N。\n",
    "\n",
    "给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。\n",
    "\n",
    "现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。\n",
    "\n",
    "注意:\n",
    "\n",
    "N 的范围在 [1, 100] 之间。\n",
    "K 的范围在 [1, N] 之间。\n",
    "times 的长度在 [1, 6000] 之间。\n",
    "所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/directweightedgraph.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "times = [(0,1,20), (0,2,15),\n",
    "         (1,0,2), (1,4,10), (1,5,30),\n",
    "         (2,1,4), (2,5,10),\n",
    "         (4,3,15),\n",
    "         (5,3,4), (5,4,10)\n",
    "        ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "\n",
    "# 使用Dijkstra算法，不断更新（离起点）最近节点的相邻节点\n",
    "def network_delay_time(times, N, K):\n",
    "    \n",
    "    # 将边权重列表转换为邻接表\n",
    "    def get_graph(times, N):\n",
    "        graph = {}\n",
    "        for i in range(N):\n",
    "            graph[i] = {}\n",
    "        for begin, end, weight in times:\n",
    "            if begin not in graph: graph[begin] = {}\n",
    "            if end not in graph: graph[end] = {}\n",
    "            graph[begin][end] = weight\n",
    "        return graph\n",
    "    \n",
    "    graph = get_graph(times, N)\n",
    "    processed = set() # 记录已经确定最短路径的节点\n",
    "    costs = {} # 记录每个节点的临时最短路径\n",
    "    heap = [] # 最小堆，储存每个节点的临时最短路径\n",
    "    \n",
    "    costs[K] = 0\n",
    "    heappush(heap, (0, K))\n",
    "    \n",
    "    while heap:\n",
    "        cost, cur_node = heappop(heap) # 从堆顶取出当前最短路径\n",
    "        while cur_node in processed:\n",
    "            if not heap: break\n",
    "            cost, cur_node = heappop(heap)\n",
    "        if cur_node in processed: break\n",
    "        # 对当前节点的所有相邻节点，更新起点到相邻节点的最短路\n",
    "        for adj_node in graph[cur_node]:\n",
    "            if adj_node in processed: continue # 跳过已确定最短路径的节点\n",
    "            new_cost = cost + graph[cur_node][adj_node] # 新距离 = 已确定的当前节点距离 + 邻边长度\n",
    "            if adj_node in costs and new_cost >= costs[adj_node]: continue # 原有路径更短则无需更新\n",
    "            costs[adj_node] = new_cost\n",
    "            heappush(heap, (new_cost, adj_node))\n",
    "        processed.add(cur_node) # 将当前节点标记为已经确定最短路径的节点\n",
    "        \n",
    "    if len(processed) < N: return -1\n",
    "    \n",
    "    max_cost = max([costs[i] for i in processed]) # 最大的最短路径距离，即为所有节点收到信号的时间\n",
    "    \n",
    "    return max_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "network_delay_time(times, 6, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "network_delay_time(times, 6, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "network_delay_time(times, 6, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "network_delay_time(times, 6, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 207. 课程表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在你总共有 n 门课需要选，记为 0 到 n-1。\n",
    "\n",
    "在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "\n",
    "给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: 2, [[1,0]] \n",
    "输出: true\n",
    "\n",
    "解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。\n",
    "示例 2:\n",
    "\n",
    "输入: 2, [[1,0],[0,1]]\n",
    "输出: false\n",
    "\n",
    "解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。\n",
    "\n",
    "说明:\n",
    "\n",
    "输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。\n",
    "你可以假定输入的先决条件中没有重复的边。\n",
    "\n",
    "提示:\n",
    "\n",
    "这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。\n",
    "通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。\n",
    "拓扑排序也可以通过 BFS 完成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 深度优先遍历\n",
    "def can_finish(num_courses, prerequisites):\n",
    "    graph = {} # 邻接表\n",
    "    visited = {} # 访问状态 0-未访问 1-已访问过 2-正在遍历中\n",
    "    \n",
    "    # 生成邻接表\n",
    "    for i in range(num_courses):\n",
    "        graph[i] = set()\n",
    "        visited[i] = 0\n",
    "    \n",
    "    for end, begin in prerequisites:\n",
    "        graph[begin].add(end)\n",
    "    \n",
    "    # 深度优先遍历，判断是否有环\n",
    "    def dfs(node):\n",
    "        if visited[node] == 2: return True # 遇到正在遍历的节点，表示存在环\n",
    "        if visited[node] != 0: return False # 遇到已经访问过的节点，结束访问\n",
    "        \n",
    "        visited[node] = 2 # 标记为正在遍历\n",
    "        for successor in graph[node]:\n",
    "            if dfs(successor): # 遇到环\n",
    "                return True\n",
    "        \n",
    "        visited[node] = 1 # 标记为已访问\n",
    "        return False\n",
    "    \n",
    "    for node in graph:\n",
    "        if dfs(node): return False\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(2, [[1,0], [0,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(4, [[1,0], [2,1], [3,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(3, [[0,2], [1,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(4, [[1,0], [2,1], [3,2], [0,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(4, [[1,0], [2,1], [0,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(4, [[1,0], [3,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_finish(1, [])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 210. 课程表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在你总共有 n 门课需要选，记为 0 到 n-1。\n",
    "\n",
    "在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "\n",
    "给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。\n",
    "\n",
    "可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: 2, [[1,0]] \n",
    "输出: [0,1]\n",
    "\n",
    "解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。\n",
    "示例 2:\n",
    "\n",
    "输入: 4, [[1,0],[2,0],[3,1],[3,2]]\n",
    "输出: [0,1,2,3] or [0,2,1,3]\n",
    "\n",
    "解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。\n",
    "     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。\n",
    "说明:\n",
    "\n",
    "输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。\n",
    "你可以假定输入的先决条件中没有重复的边。\n",
    "\n",
    "提示:\n",
    "\n",
    "这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。\n",
    "通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。\n",
    "拓扑排序也可以通过 BFS 完成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拓扑排序，每一次都输出入度为 0 的结点，并移除它、修改它指向的结点的入度，依次得到的结点序列就是拓扑排序的结点序列\n",
    "def find_order(num_courses, prerequisites):\n",
    "    in_degrees = {} # 入度表\n",
    "    graph = {} # 邻接表\n",
    "    \n",
    "    # 生成入度表和邻接表\n",
    "    for i in range(num_courses):\n",
    "        in_degrees[i] = 0    \n",
    "        graph[i] = set()\n",
    "    \n",
    "    for end, begin in prerequisites:\n",
    "        in_degrees[end] += 1   \n",
    "        graph[begin].add(end)\n",
    "        \n",
    "    queue = [] # 存放入度为0的节点的队列\n",
    "    for node in in_degrees:\n",
    "        if in_degrees[node] == 0:\n",
    "            queue.append(node)\n",
    "    \n",
    "    res = [] # 访问序列\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        res.append(node)\n",
    "        \n",
    "        # 遍历后继节点，并使其入度减1，如果入度为0，则加入队列\n",
    "        for successor in graph[node]:\n",
    "            in_degrees[successor] -= 1\n",
    "            if in_degrees[successor] == 0:\n",
    "                queue.append(successor)\n",
    "    \n",
    "    # 结果序列未包含所有节点，说明有环\n",
    "    if len(res) != num_courses:\n",
    "        return []\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(2, [[1,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(4, [[1,0],[2,0],[3,1],[3,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(4, [[1,0], [2,1], [3,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 0, 1]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(3, [[0,2], [1,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(4, [[1,0], [2,1], [3,2], [0,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(4, [[1,0], [2,1], [0,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 1, 3]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(4, [[1,0], [3,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_order(1, [])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 630. 课程表 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。\n",
    "\n",
    "给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。\n",
    "\n",
    " \n",
    "\n",
    "示例：\n",
    "\n",
    "输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]\n",
    "输出: 3\n",
    "\n",
    "解释: \n",
    "这里一共有 4 门课程, 但是你最多可以修 3 门:\n",
    "首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。\n",
    "第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。\n",
    "第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。\n",
    "第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。\n",
    " \n",
    "\n",
    "提示:\n",
    "\n",
    "整数 1 <= d, t, n <= 10,000 。\n",
    "你不能同时修两门课程。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 深度优先搜索\n",
    "def schedule_course(courses):\n",
    "    \n",
    "    # dfs表示当前时间能学完的最多剩余课程\n",
    "    def dfs(time, left_courses):\n",
    "        # 从剩余课程中找出所有符合要求的课程\n",
    "        max_count = 0\n",
    "        for course in left_courses:\n",
    "            cost, deadline = courses[course]\n",
    "            if time <= deadline - cost:\n",
    "                next_courses = left_courses.copy()\n",
    "                next_courses.remove(course)\n",
    "                max_count = max(max_count, 1 + dfs(time + cost, next_courses))\n",
    "        return max_count\n",
    "    \n",
    "    res = dfs(0, [i for i in range(len(courses))])\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course([[100, 200], [100, 200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course([[100, 200], [101, 200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 动态规划，贪心算法\n",
    "def schedule_course2(courses):\n",
    "    if not courses: return 0\n",
    "    \n",
    "    num_courses = len(courses)\n",
    "    \n",
    "    # 按照结束时间排序，若结束时间相同，则用时短的在前\n",
    "    sorted_courses = sorted(courses, key=lambda x:(x[1], x[0]))\n",
    "    \n",
    "    # dp[i]表示学完i门课需要的最短时间\n",
    "    dp = [float('inf')] * (num_courses + 1)\n",
    "    dp[0] = 0\n",
    "    \n",
    "    res = 0 # 记录最多可以学的课程数\n",
    "    for i in range(num_courses):\n",
    "        t, d = sorted_courses[i]\n",
    "        for j in reversed(range(i + 1)): # 从后往前更新\n",
    "            new_dp = t + dp[j]\n",
    "            # 如果这节课可以在结束时间上完，并且时长小于之前的（贪心），则优化\n",
    "            if new_dp <= d and new_dp < dp[j + 1]:\n",
    "                dp[j + 1] = new_dp\n",
    "                res = max(res, j + 1)\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course2([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course2([[100, 200], [100, 200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course2([[100, 200], [101, 200]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_course2([])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 329. 矩阵中的最长递增路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个整数矩阵，找出最长递增路径的长度。\n",
    "\n",
    "对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: nums = \n",
    "[\n",
    "  [9,9,4],\n",
    "  [6,6,8],\n",
    "  [2,1,1]\n",
    "] \n",
    "输出: 4 \n",
    "\n",
    "解释: 最长递增路径为 [1, 2, 6, 9]。\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: nums = \n",
    "[\n",
    "  [3,4,5],\n",
    "  [3,2,6],\n",
    "  [2,2,1]\n",
    "] \n",
    "输出: 4 \n",
    "\n",
    "解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 记忆化深度优先搜索\n",
    "def longest_increasing_path(matrix):\n",
    "    if not matrix or not matrix[0]: return 0\n",
    "    \n",
    "    direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "    width = len(matrix[0])\n",
    "    height = len(matrix)\n",
    "    cache = [[0] * width for i in range(height)]\n",
    "    \n",
    "    def dfs(x, y):\n",
    "        if cache[y][x] > 0: return cache[y][x]\n",
    "        max_dis = 0\n",
    "        for ix, iy in direct:\n",
    "            nx, ny = x + ix, y + iy\n",
    "            if nx < 0 or nx >= width or ny < 0 or ny >= height: continue\n",
    "            if matrix[ny][nx] > matrix[y][x]:\n",
    "                max_dis = max(max_dis, dfs(nx, ny))\n",
    "        cache[y][x] = 1 + max_dis\n",
    "        return cache[y][x]\n",
    "    \n",
    "    res = 0\n",
    "    for y in range(height):\n",
    "        for x in range(width):\n",
    "            res = max(res, dfs(x, y))\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = [[9,9,4], [6,6,8], [2,1,1]]\n",
    "longest_increasing_path(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = [[3,4,5], [3,2,6], [2,2,1]]\n",
    "longest_increasing_path(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拓扑排序，每一次都输出出度为 0 的结点（叶子），并移除它、修改指向它的结点的出度，统计其遍历深度\n",
    "def longest_increasing_path2(matrix):\n",
    "    if not matrix or not matrix[0]: return 0\n",
    "    \n",
    "    direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "    width = len(matrix[0])\n",
    "    height = len(matrix)    \n",
    "    out_degrees = [[0] * width for i in range(height)] # 出度表\n",
    "    queue = [] # 出度为0的节点队列\n",
    "    \n",
    "    # 计算所有节点的出度\n",
    "    for y in range(height):\n",
    "        for x in range(width):\n",
    "            for ix, iy in direct:\n",
    "                nx, ny = x + ix, y + iy\n",
    "                if nx >= 0 and nx < width and ny >= 0 and ny < height and matrix[ny][nx] > matrix[y][x]:\n",
    "                    out_degrees[y][x] += 1\n",
    "    \n",
    "    # 将出度为0的节点加入队列\n",
    "    for y in range(height):\n",
    "        for x in range(width):\n",
    "            if out_degrees[y][x] == 0:\n",
    "                queue.append((x, y))\n",
    "    \n",
    "    height = 0 # 遍历深度\n",
    "    while queue:\n",
    "        height += 1\n",
    "        new_queue = [] # 新队列\n",
    "        # 遍历队列中所有节点的前驱节点\n",
    "        for x, y in queue:\n",
    "            for ix, iy in direct:\n",
    "                px, py = x + ix, y + iy\n",
    "                if px >= 0 and px < width and py >= 0 and py < height and matrix[py][px] < matrix[y][x]:\n",
    "                    out_degrees[py][px] -= 1\n",
    "                    if out_degrees[py][px] == 0:\n",
    "                        new_queue.append((px, py)) # 如果前驱节点的出度变为0，则加入新队列\n",
    "        queue = new_queue\n",
    "    \n",
    "    return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = [[9,9,4], [6,6,8], [2,1,1]]\n",
    "longest_increasing_path2(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = [[3,4,5], [3,2,6], [2,2,1]]\n",
    "longest_increasing_path2(matrix)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
